package ai.zixing.mashibing.basic_class.class12;

/**
 * 请同学们自行搜索或者想象一个象棋的棋盘，
 * 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
 * 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
 * 给你三个 参数 x，y，k
 * 返回“马”从(0,0)位置出发，必须走k步
 * 最后落在(x,y)上的方法数有多少种?
 */
public class Code07_HorseJump {

    public static int ways(int a, int b, int step) {
        return f(0, 0, step, a, b);
    }

    // (x, y) 当前坐标, (a, b) 目标坐标
    // step 还能走多少步
    public static int f(int x, int y, int step, int a, int b) {
        if (y < 0 || y > 9 || x < 0 || x > 8) {
            return 0;
        }
        if (step == 0) {
            return (x == a && y == b) ? 1 : 0;
        }
        return f(x + 2, y + 1, step - 1, a, b)
                + f(x + 1, y + 2, step - 1, a, b)
                + f(x - 1, y + 2, step - 1, a, b)
                + f(x - 2, y + 1, step - 1, a, b)
                + f(x - 2, y - 1, step - 1, a, b)
                + f(x - 1, y - 2, step - 1, a, b)
                + f(x + 1, y - 2, step - 1, a, b)
                + f(x + 2, y - 1, step - 1, a, b);
    }

    private static int waysdp(int a, int b, int s) {
        int[][][] dp = new int[9][10][s + 1];
        // 到(a, b)没有步数的时候是 1 种
        dp[a][b][0] = 1;
        // 层
        for (int step = 1; step <= s; step++) {
            // 行
            for (int y = 0; y < 10; y++) {
                for (int x = 0; x < 9; x++) {
                    dp[x][y][step] = getValue(dp, x + 2, y + 1, step - 1)
                            + getValue(dp, x + 1, y + 2, step - 1)
                            + getValue(dp, x - 1, y + 2, step - 1)
                            + getValue(dp, x - 2, y + 1, step - 1)
                            + getValue(dp, x - 2, y - 1, step - 1)
                            + getValue(dp, x - 1, y - 2, step - 1)
                            + getValue(dp, x + 1, y - 2, step - 1)
                            + getValue(dp, x + 2, y - 1, step - 1);
                }
            }
        }
        return dp[0][0][s];
    }

    private static int getValue(int[][][] dp, int i, int j, int step) {
        if (i < 0 || j < 0 || i > 8 || j > 9) {
            return 0;
        }
        return dp[i][j][step];
    }


    /**
     * 当前来到 row， col位置，还剩 rest 步，走完rest步之后，到 x， y
     */
    public static int p(int row, int col, int rest, int x, int y) {
        if (rest == 0) {
            return row == x && col == y ? 1 : 0;
        }
        if (row < 0 || row > 9 || col < 0 || col > 8) {
            return 0;
        }
        return p(row + 2, col - 1, rest - 1, x, y)
                + p(row + 2, col + 1, rest - 1, x, y)
                + p(row + 1, col + 2, rest - 1, x, y)
                + p(row + 1, col - 2, rest - 1, x, y)
                + p(row - 2, col + 1, rest - 1, x, y)
                + p(row - 2, col - 1, rest - 1, x, y)
                + p(row - 1, col + 2, rest - 1, x, y)
                + p(row - 1, col - 2, rest - 1, x, y);

    }

    public static int way3(int x, int y, int k) {
        return p(0, 0, k, x, y);
    }

    public static void main(String[] args) {
        int x = 7;
        int y = 7;
        int step = 10;
        System.out.println(ways(x, y, step));
        System.out.println(waysdp(x, y, step));
        System.out.println(way3(x, y, step));
    }
}
